package com.lfg.leetcode.leetcode300;


public class No354maxEnvelopes {
    public static void main(String[] args) {
//        int ret = maxEnvelopes(new int[][]{
//                new int[]{1, 3},
//                new int[]{3, 5},
//                new int[]{6, 7},
//                new int[]{6, 8},
//                new int[]{8, 4},
//                new int[]{9, 5}
//        });

        int ret = maxEnvelopes(new int[][]{
                new int[]{10, 8},
                new int[]{1, 12},
                new int[]{6, 15},
                new int[]{2, 18}
        });
        System.out.println(ret);

    }

    public static int maxEnvelopes(int[][] envelopes) {
        if (envelopes.length == 0) {
            return 0;
        } else if (envelopes.length == 1) {
            return 1;
        }
        sortArray(envelopes, 0, envelopes.length - 1);
        int[] dp = new int[envelopes.length];
        dp[0] = 1;
        int ret = 1;
        for (int i = 1; i < envelopes.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (envelopes[i][0] > envelopes[j][0] && envelopes[i][1] > envelopes[j][1]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            ret = Math.max(ret, dp[i]);
        }
        return ret;
    }

    public static void sortArray(int[][] envelopes, int start, int end) {
        if (start >= end) {
            return;
        }
        int begin = start;
        int finish = end;
        int index = (start + end) / 2;
        while (start < end) {
            while (start < index && compare(envelopes[start], envelopes[index]) <= 0) {
                start++;
            }
            int[] tmp = envelopes[index];
            envelopes[index] = envelopes[start];
            envelopes[start] = tmp;
            index = start;

            while (index < end && compare(envelopes[end], envelopes[index]) >= 0) {
                end--;
            }
            tmp = envelopes[index];
            envelopes[index] = envelopes[end];
            envelopes[end] = tmp;
            index = end;
        }
        sortArray(envelopes, begin, index - 1);
        sortArray(envelopes, index + 1, finish);
    }

    public static int compare(int[] array1, int[] array2) {
        if (array1[0] == array2[0]) {
            if (array1[1] == array2[1]) {
                return 0;
            } else if (array1[1] > array2[1]) {
                return 1;
            } else {
                return -1;
            }
        } else if (array1[0] > array2[0]) {
            return 1;
        } else {
            return -1;
        }
    }
}



